package 力扣.回溯;

import java.util.*;

import static 力扣.堆.堆排序.swap;

public class 全排列46 {
    public List<List<Integer>> permute(int[] nums) {
         if (nums == null){
             return new ArrayList<>();
         }
         List<List<Integer>> ans = new ArrayList<>();
         List<Integer> box = new ArrayList<>();
         Boolean[] used = new Boolean[nums.length];
         Arrays.fill(used, false);
         backTrace(nums,0,used,ans,box);
         return ans;
    }

    /**方法一
     * 通过使用布尔数组used[]来对已经使用的元素进行标识
     * @param nums
     * @param i
     * @param used
     * @param ans
     * @param box
     */
    private void backTrace(int[] nums, int i, Boolean[] used,List<List<Integer>> ans, List<Integer> box) {
        int N = nums.length;
        if (i == N){
            ans.add(new ArrayList<>(box));
        }
        if (i >= N){
            return;
        }
        for (int j = 0; j < N; j++) {
            if (!used[j]){//没用过
                int t = nums[j];
                box.add(t);
                used[j] = true;
                backTrace(nums,  i + 1,used, ans, box);
                used[j] = false;
                box.remove(box.remove(box.size() - 1));
            }
        }
    }
    /**方法一的缺点：每次都遍历整个数组，有点浪费时间
     *
     * 方法二
     * 本题难点：已经使用的数字不能再继续使用，需要跳过，方法一利用数组used[]对每个已使用元素进行标识
     * 有没有更好的办法呢？
     * 有！交换法
     * 核心思想：对已经使用的数字交换到数组的左边，没有使用的数字交换到数组的右边，该如何做呢？
     * 技巧：对于本题因为每次挑选的宝石都是自身，所以可以使用排队的思想：每次交换每个人的位置
     * 例子：比如想给第二位置安排一个人进去（第二个位置原先就有人）：我们想让队列中第四个人过去，就得让第四个人和第二个人交换一个位置。
     *     此时左边前两个位置确定有了人，右边都是没确定的！满足上面的核心思想！
     */
    public List<List<Integer>> permute2(int[] nums) {
        if (nums == null){
            return new ArrayList<>();
        }
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> box = new ArrayList<>();
        backTrace2(nums,0,ans,box);
        return ans;
    }

    private void backTrace2(int[] nums, int i, List<List<Integer>> ans, List<Integer> box) {
        int N = nums.length;
        if (i == N){
            ans.add(new ArrayList<>(box));
        }
        if (i >= N){
            return;
        }
        for (int j = i; j < N; j++) {
            int t = nums[j];
            box.add(t);
            swap(nums,j,i);
            backTrace2(nums, i + 1, ans, box);
            swap(nums, i, j);
            box.remove(box.size() - 1);
        }
    }

    private void swap(int[] nums, int i, int j) {
         int t = nums[i];
         nums[i] = nums[j];
         nums[j] = t;
    }

}
